package com.waiting.leetcode;

import java.util.*;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/14
 **/
public class RepeatedDNASequences187 {
    public static void main(String[] args) {
        String s = "AAAAAAAAAAA";
        List<String> result = findRepeatedDnaSequences(s);
        for (String item : result) {
            System.out.println(item);
        }
        System.out.println("over");
    }

    public static List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new LinkedList<>();
        Map<String, Integer> subStringMap = new HashMap<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String subString = s.substring(i, i + 10);
            subStringMap.put(subString, subStringMap.getOrDefault(subString, 0) + 1);
        }
        for (Map.Entry<String, Integer> item : subStringMap.entrySet()) {
            if (item.getValue() >= 2) {
                result.add(item.getKey());
            }
        }
        return result;
    }

    public List<String> findRepeatedDnaSequences2(String s) {
        Set<Integer> words = new HashSet<>();
        Set<Integer> doubleWords = new HashSet<>();
        List<String> rv = new ArrayList<>();
        char[] map = new char[26];
        //map['A' - 'A'] = 0;
        map['C' - 'A'] = 1;
        map['G' - 'A'] = 2;
        map['T' - 'A'] = 3;

        for(int i = 0; i < s.length() - 9; i++) {
            int v = 0;
            for(int j = i; j < i + 10; j++) {
                v <<= 2;
                v |= map[s.charAt(j) - 'A'];
            }
            if(!words.add(v) && doubleWords.add(v)) {
                rv.add(s.substring(i, i + 10));
            }
        }
        return rv;
    }
}
